/*
 *  Input: array.
 *  Output: sum of all three integer set is 0. Non duplicate. 
 * */
import java.io.*;
import java.util.*;

public class threeSumSolution {
	public ArrayList<ArrayList<Integer>> threeSum (int[] array) {
	    try {
            if (array == null)
                throw new NullPointerException ();
			/* Sort the array. */
			Arrays.sort (array);
			/* The answer set. */
		    ArrayList<ArrayList<Integer>> arrayOfArray = new ArrayList<ArrayList<Integer>> ();
		    int[] index = new int[3];
		    while (index[0] < array.length) {
		        /* Ever iteration, array[index[0]] is increasing. */
		    	/* Two pointers. */
		    	index[1] = index[0] + 1;
		        index[2] = array.length - 1;
		        while (index[1] < index[2]) {
		            int sum = 0;
		            for (int i = 0; i < 3; ++i)
		                sum += array[index[i]];
		            if (sum == 0) {
		                ArrayList<Integer> subSet = new ArrayList<Integer> ();
		                for (int i = 0; i < 3; ++i)
		                    subSet.add (array[index[i]]);
		                arrayOfArray.add (subSet);
		                /* Jump to next. */
		                int next = index[1] + 1;
		                while (next < index[2] && array[next] == array[index[1]])
		                    ++next;
		                index[1] = next;
		                next = index[2] - 1;
		                while (next > index[1] && array[next] == array[index[2]])
		                    --next;
		                index[2] = next;
		            } else if (sum > 0) {
		                --index[2];
		            } else if (sum < 0) {
		                ++index[1];
		            }
		        }
		        int next = index[0] + 1;
		        while (next < array.length && array[next] == array[index[0]])
		            ++next;
		        index[0] = next;
		    }
		    return arrayOfArray;
	    } catch (Exception e) {
	    	e.printStackTrace();
	    	return null;
	    }
	}
}
